10893. Калькулятор

Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число 1. Помогите Илье определить наименьшее количество действий, после которой он получит число n.

Вход. Одно число n (10 ≤ n ≤ 10⁹).

Выход. Выведите наименьшее количество операций.

Пример входа	Пример выхода
1447	16

РЕШЕНИЕ

жадность

Анализ алгоритма

Двигаемся жадным образом от числа n к 1:

· если n делится на 3, то делим его на 3;

· иначе вычитаем из n единицу;

Пример

Пусть n = 21. Получить 1 за наименьшее количество операций (за четыре) можно следующим образом:

21 → 7 → 6 → 2 → 1

Реализация алгоритма

Читаем входное значение n.

scanf("%d", &n);

В переменной cnt подсчитываем число выполненных операций.

cnt = 0;

Жадным образом двигаемся от n к 1.

while (n > 1)

{

if (n % 3 == 0) n /= 3;

else n--;

cnt++;

}

Выводим ответ.

printf("%d\n", cnt);

Python реализация

Читаем входное значение n.

n = int(input())

В переменной cnt подсчитываем число выполненных операций.

cnt = 0

Жадным образом двигаемся от n к 1.

while n > 1:

if n % 3 == 0:

n //= 3

else:

n -= 1

cnt += 1

Выводим ответ.

print(cnt)